package com.chapter4.graph.direct;

import com.chapter1.basic.bag.Bag;
import com.util.In;

/** 
 * @ClassName: Digraph 
 * @Description: 无向图api
 * @author minjun minjun@bw30.com
 * @date 2015-2-27 下午2:08:25 
 *  
 */
public class Digraph {

	private Bag<Integer>[] bags;
	
	private final int v;
	
	private int e;
	
	@SuppressWarnings("unchecked")
	public Digraph(int v){
		this.v=v;
		bags=(Bag<Integer>[])new Bag[v];
		for(int i=0;i<v;i++){
			bags[i]=new Bag<Integer>();
		}
	}
	
	public Digraph(In in){
		this(in.readInt());
		int E=in.readInt();
		for(int i=0;i<E;i++){
			addEdge(in.readInt(), in.readInt());
		}
	}
	
	public void addEdge(int v,int w){
		bags[v].add(w);
		e++;
	}
	
	public Iterable<Integer> adj(int v){
		return bags[v];
	}
	
	/**
	 * 
	* @Title: reverse 
	* @Description: 反转所有路径方向 
	* @param @return    设定文件 
	* @return Digraph    返回类型 
	* @throws
	 */
	public Digraph reverse(){
		Digraph d=new Digraph(v);
		for(int i=0;i<v;i++){
			for(int w:adj(i)){
				d.addEdge(w, i);
			}
		}
		return d;
	}
	
	public int E(){
		return e;
	}
	
	public int V(){
		return v;
	}
	
	@Override
	public String toString(){
		StringBuilder sb=new StringBuilder();
		for(int i=0;i<v;i++){
			for(int w:adj(i)){
				sb.append(i+"->"+w+"\n");
			}
		}
		return sb.toString();
	}
}
